class Solution {
public:
    /*
    *使用KMP算法
    */

   //现在整体判断
    int strStr(string haystack, string needle) {
        if ((needle.length()==0)&&(!haystack.empty())||(haystack.empty()&&needle.empty()))
        {
            return 0;
        }
        if(haystack.length()<needle.length()||haystack.empty()||needle.empty()||haystack.length()==0){
            return -1;
        }
    
        return KMP(haystack,needle);

    }
private:
    //使用KMP算法
    int KMP(const string& haystack, const string& needle){
        int m = haystack.length();
        int n = needle.length();
        vector<int> prefix(n,0);
        
        //初始化 匹配数组next
        prefix_table(prefix,needle);

        //开始查找
        int i=0,j=0;
        while(i<m){
            if(haystack[i]==needle[j]){
                ++i;
                ++j;
            }
            else
            {
                if(j==0){
                    ++i;
                }
                else
                {
                    j=prefix[j-1];
                }
            }
            if(j==n){
                return i-j;
            }   
        }
           return -1;
    }

    void prefix_table(vector<int>& next,const string& needle){
        next[0]=0;
        int n = needle.length();
        int i=1,j=0;
        while(i<n){
            if(needle[j]==needle[i]){
                ++j;
                next[i]=j;
                ++i;
            }
            else
            {
                if(j==0){
                    next[i]=0;
                    ++i;
                }
                else{
                    j=next[j-1];
                }
            }
            
        }

    }
};